
/**
 * @Project : Clion_ProgrammingExercises
 * @File : 0022
 * @Author : WangRuoyu 
 * @Date : 2023/5/27 11:24
 */

#include <vector>
#include "iostream"
#include "unordered_set"

using namespace std;

class Solution {
public:
    unordered_set<string> set;
    int k;

    void dfs(string s, int pos, int neg) {
        if (pos < neg) {
            return;
        }
        if (pos == k && neg == k) {
            set.insert(s);
            return;
        }
        if (pos < k) {
            dfs(s + '(', pos + 1, neg);
        }
        if (neg < k) {
            dfs(s + ')', pos, neg + 1);
        }
    }

    vector<string> generateParenthesis(int n) {
        k = n;
        dfs("", 0, 0);
        return vector<string>(set.begin(), set.end());
    }
};

int main() {
    Solution sl;
    for (string s: sl.generateParenthesis(3)) {
        cout << s << " ";
    }
    return 0;
}